---
id: 5900f51f1000cf542c510031
title: 'Завдання 434: жорсткі графи'
challengeType: 1
forumTopicId: 302105
dashedName: problem-434-rigid-graphs
---

# --description--

Пригадайте, що граф — це набір вершин та ребер, які з’єднують ці вершини. Дві вершини, з’єднані ребром, називаються прилеглими.

Графи можна вбудувати в Евклідів простір, призначивши кожній вершині точку Евклідового простору.

Гнучкий граф — це граф, вершини якого можна переміщувати неперервно так, що відстань між принаймні двома несуміжними вершинами змінюється, а відстань між всіма парами суміжних вершин залишається незмінною.

Жорсткий граф — це граф, який не є гнучким.

Якщо просто, то граф є жорстким, якщо при повній заміні його вершин обертовими шарнірами та ребер стрижнями, які не є еластичними та не розгинаються, жодну частину графа не можна буде перемістити незалежно від решти графа.

Сітчасті графи, вбудовані в Евклідовому просторі, не є жорсткими, як зображено на анімації:

<img class="img-responsive center-block" alt="анімація з сітчастими графами в Евклідовому просторі, які не є жорсткими" src="https://cdn.freecodecamp.org/curriculum/project-euler/rigid-graphs-1.gif" style="background-color: white; padding: 10px;" />

Однак їх можна зробити жорсткими, додавши діагональні ребра до сіток. Наприклад, для сітчастого графа 2×3 існує 19 способів зробити граф жорстким:

<img class="img-responsive center-block" alt="19 способів зробити сітчастий граф 2х3 жорстким" src="https://cdn.freecodecamp.org/curriculum/project-euler/rigid-graphs-2.png" style="background-color: white; padding: 10px;" />

Зверніть увагу, що у цьому завданні ми не розглядаємо зміну напряму діагонального ребра або додавання обох діагональних ребер до сітки як інший спосіб зробити сітчастий граф жорстким.

Нехай $R(m, n)$ буде кількістю способів зробити сітчастий граф $m × n$ жорстким.

Наприклад, $R(2, 3) = 19$ та $R(5, 5) = 23\\,679\\,901$.

Визначимо $S(N)$ як $\sum R(i, j)$ за умови $1 ≤ i$, $j ≤ N$.

Наприклад, $S(5) = 25\\,021\\,721$.

Знайдіть $S(100)$. Надайте відповідь за модулем $1\\,000\\,000\\,033$.

# --hints--

`rigidGraphs()` має повернути `863253606`.

```js
assert.strictEqual(rigidGraphs(), 863253606);
```

# --seed--

## --seed-contents--

```js
function rigidGraphs() {

  return true;
}

rigidGraphs();
```

# --solutions--

```js
// solution required
```
